package cn.myworld.algorithm.opt;

import cn.myworld.algorithm.linear.Queue;

public class PagerFolding {

    public static void main(String[] args) {
        Node<String> tree  = createTree(2);
        printTree(tree);
    }

    private static class Node<T> {

        public T data;

        public Node<T> left;
        public Node<T> right;

        public Node(T data,  Node<T> left, Node<T> right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }

    }
    // 模拟N次对折，产生树
    private static Node<String> createTree(int N) {
        // 定义根节点
        Node<String> root = null;

        for (int i = 0; i < N; i++) {
            // 当前是第一次对折
            if (i == 0) {
                root = new Node<String>("down", null, null);
                continue;
            }

            // 当前不是第一次对折
            // 定义一个辅助队列，通过层序遍历思想，找到叶子节点，叶子节点添加子节点
            Queue<Node<String>>  queue = new Queue<Node<String>>();
            queue.enqueue(root);

            // 循环遍历队列
            while (!queue.isEmpty()) {
                // 从队列中弹出一个节点
                Node<String> node = queue.dequeue();
                if (node.left != null) {
                    queue.enqueue(node.left);
                }
                if (node.right != null) {
                    queue.enqueue(node.right);
                }
                // 如果同时没有左子节点和右子节点，证明是叶子节点，只需要给该节点添加左右子节点
                if (node.left == null && node.right == null) {
                    node.left = new Node<String>("down", null, null);
                    node.right = new Node<String>("up", null, null);
                }
            }
        }
        return root;
    }

    // 打印树中的节点到控制台
    private static void printTree(Node<String> root) {
        // 中序遍历
        if (root == null) {
            return;
        }
        if (root.left != null) {
            printTree(root.left);
        }
        System.out.println(root.data + " ");
        if (root.right != null) {
            printTree(root.right);
        }
    }

}
